/*-------------------------------------------------------------------------
 *
 * geo_spgist.c
 *	  SP-GiST 实现的四维四叉树。
 *
 * 此模块提供了对使用四叉树模拟的矩形的 SP-GiST 实现。SP-GiST 不允许对重叠对象进行索引。我们在四维空间中使二维对象永不重叠。与作为 GiST 实现的传统 R-树相比，该技术具有一些优点。性能测试表明，此技术对于重叠对象过多的情况（即“意大利面条数据”）特别有效。
 *
 * 与原始四叉树不同，我们将树分为四维空间中的 16 个象限。更容易想象的是将空间分成 4 的两次：
 *
 *				|	   |
 *				|	   |
 *				| -----+-----
 *				|	   |
 *				|	   |
 * -------------+-------------
 *				|
 *				|
 *				|
 *				|
 *				|
 *
 * 我们使用框数据类型作为前缀，但我们将它们视为四维空间中的点，因为二维矩形不足以表示四维空间中的象限边界。它们足够指示下一个象限的额外边界。
 *
 * 我们使用 SP-GiST 提供的遍历值在遍历树时计算并存储象限的边界。遍历值包含四维空间中的所有边界，并能够将所需的边界传递给后续的遍历值。总之，计算下一个遍历值需要三件事：
 *
 *	(1) 父节点的遍历值
 *	(2) 当前节点的象限
 *	(3) 当前节点的前缀
 *
 * 如果我们在我们的简化图中进行可视化（参见上面的图）；(1) 的传递边界将是外轴，(2) 的相关部分将是另一轴的右上部分，(3) 将是内轴。
 *
 * 例如，考虑重叠的情况。当递归深入树时，当前节点中的所有象限将被检查以检查重叠。所有象限的边界都将重新计算。重叠检查回答的问题是：这个象限中的任何框是否可以与给定框重叠？如果是，那么这个象限将被遍历。如果没有，那么这个象限将被跳过。
 *
 * 此方法为树的每一个角落的每一个维度提供了最小值和最大值的限制，除了根节点。在根节点，我们设置尚不存在的边界为无穷大。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *			src/backend/utils/adt/geo_spgist.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "access/spgist.h"
#include "access/spgist_private.h"
#include "access/stratnum.h"
#include "catalog/pg_type.h"
#include "utils/float.h"
#include "utils/fmgroids.h"
#include "utils/fmgrprotos.h"
#include "utils/geo_decls.h"

/*
 * qsort 的比较器
 *
 * 我们不需要在这里使用浮点宏，因为这只会在影响索引性能的地方使用，
 * 而不是影响正确性。
 */
static int fc_compareDoubles(const void *fc_a, const void *fc_b)
{
	float8		fc_x = *(float8 *) fc_a;
	float8		fc_y = *(float8 *) fc_b;

	if (fc_x == fc_y)
		return 0;
	return (fc_x > fc_y) ? 1 : -1;
}

typedef struct
{
	float8		low;
	float8		high;
} Range;

typedef struct
{
	Range		left;
	Range		right;
} RangeBox;

typedef struct
{
	RangeBox	range_box_x;
	RangeBox	range_box_y;
} RectBox;

/*
 * 计算象限
 *
 * 象限是一个 8 位无符号整数，使用 4 个最低位。
 * 此函数接受 BOX 作为输入。它们尚未转换为 RangeBoxes。
 * 通过比较 box 的一个角来设置所有 4 个位。这总共形成 16 个象限。
 */
static uint8 fc_getQuadrant(BOX *fc_centroid, BOX *fc_inBox)
{
	uint8		fc_quadrant = 0;

	if (fc_inBox->low.x > fc_centroid->low.x)
		fc_quadrant |= 0x8;

	if (fc_inBox->high.x > fc_centroid->high.x)
		fc_quadrant |= 0x4;

	if (fc_inBox->low.y > fc_centroid->low.y)
		fc_quadrant |= 0x2;

	if (fc_inBox->high.y > fc_centroid->high.y)
		fc_quadrant |= 0x1;

	return fc_quadrant;
}

/*
 * 使用 BOX 获取 RangeBox
 *
 * 我们将 BOX 转换为我们的结构，以强调它们在 4D 空间中表示点的功能。
 * 使用此结构访问值也更加方便。
 */
static RangeBox *
fc_getRangeBox(BOX *fc_box)
{
	RangeBox   *fc_range_box = (RangeBox *) palloc(sizeof(RangeBox));

	fc_range_box->left.low = fc_box->low.x;
	fc_range_box->left.high = fc_box->high.x;

	fc_range_box->right.low = fc_box->low.y;
	fc_range_box->right.high = fc_box->high.y;

	return fc_range_box;
}

/*
 * 初始化遍历值
 *
 * 一开始，我们没有任何限制。我们必须初始化结构以覆盖整个 4D 空间。
 */
static RectBox *
fc_initRectBox(void)
{
	RectBox    *fc_rect_box = (RectBox *) palloc(sizeof(RectBox));
	float8		fc_infinity = get_float8_infinity();

	fc_rect_box->range_box_x.left.low = -fc_infinity;
	fc_rect_box->range_box_x.left.high = fc_infinity;

	fc_rect_box->range_box_x.right.low = -fc_infinity;
	fc_rect_box->range_box_x.right.high = fc_infinity;

	fc_rect_box->range_box_y.left.low = -fc_infinity;
	fc_rect_box->range_box_y.left.high = fc_infinity;

	fc_rect_box->range_box_y.right.low = -fc_infinity;
	fc_rect_box->range_box_y.right.high = fc_infinity;

	return fc_rect_box;
}

/*
 * 计算下一个遍历值
 *
 * 所有质心都被 RectBox 限制，但 SP-GiST 仅保留
 * 盒子。当我们遍历树时，必须使用质心和象限来计算 RectBox。
 */
static RectBox *
fc_nextRectBox(RectBox *fc_rect_box, RangeBox *fc_centroid, uint8 fc_quadrant)
{
	RectBox    *fc_next_rect_box = (RectBox *) palloc(sizeof(RectBox));

	memcpy(fc_next_rect_box, fc_rect_box, sizeof(RectBox));

	if (fc_quadrant & 0x8)
		fc_next_rect_box->range_box_x.left.low = fc_centroid->left.low;
	else
		fc_next_rect_box->range_box_x.left.high = fc_centroid->left.low;

	if (fc_quadrant & 0x4)
		fc_next_rect_box->range_box_x.right.low = fc_centroid->left.high;
	else
		fc_next_rect_box->range_box_x.right.high = fc_centroid->left.high;

	if (fc_quadrant & 0x2)
		fc_next_rect_box->range_box_y.left.low = fc_centroid->right.low;
	else
		fc_next_rect_box->range_box_y.left.high = fc_centroid->right.low;

	if (fc_quadrant & 0x1)
		fc_next_rect_box->range_box_y.right.low = fc_centroid->right.high;
	else
		fc_next_rect_box->range_box_y.right.high = fc_centroid->right.high;

	return fc_next_rect_box;
}

/* range_box 中的任何范围是否可以与此参数重叠？ */
static bool fc_overlap2D(RangeBox *fc_range_box, Range *fc_query)
{
	return FPge(fc_range_box->right.high, fc_query->low) &&
		FPle(fc_range_box->left.low, fc_query->high);
}

/* rect_box 中的任何矩形是否可以与此参数重叠？ */
static bool fc_overlap4D(RectBox *fc_rect_box, RangeBox *fc_query)
{
	return fc_overlap2D(&fc_rect_box->range_box_x, &fc_query->left) &&
		fc_overlap2D(&fc_rect_box->range_box_y, &fc_query->right);
}

/* range_box 中的任何范围是否可以包含此参数？ */
static bool fc_contain2D(RangeBox *fc_range_box, Range *fc_query)
{
	return FPge(fc_range_box->right.high, fc_query->high) &&
		FPle(fc_range_box->left.low, fc_query->low);
}

/* rect_box 中的任何矩形是否可以包含此参数？ */
static bool fc_contain4D(RectBox *fc_rect_box, RangeBox *fc_query)
{
	return fc_contain2D(&fc_rect_box->range_box_x, &fc_query->left) &&
		fc_contain2D(&fc_rect_box->range_box_y, &fc_query->right);
}

/* range_box 中的任何范围是否可以被此参数包含？ */
static bool fc_contained2D(RangeBox *fc_range_box, Range *fc_query)
{
	return FPle(fc_range_box->left.low, fc_query->high) &&
		FPge(fc_range_box->left.high, fc_query->low) &&
		FPle(fc_range_box->right.low, fc_query->high) &&
		FPge(fc_range_box->right.high, fc_query->low);
}

/* rect_box 中的任何矩形是否可以被此参数包含？ */
static bool fc_contained4D(RectBox *fc_rect_box, RangeBox *fc_query)
{
	return fc_contained2D(&fc_rect_box->range_box_x, &fc_query->left) &&
		fc_contained2D(&fc_rect_box->range_box_y, &fc_query->right);
}

/* range_box 中的任何范围是否可以低于此参数？ */
static bool fc_lower2D(RangeBox *fc_range_box, Range *fc_query)
{
	return FPlt(fc_range_box->left.low, fc_query->low) &&
		FPlt(fc_range_box->right.low, fc_query->low);
}

/* range_box 中的任何范围是否不能扩展到查询的右侧？ */
static bool fc_overLower2D(RangeBox *fc_range_box, Range *fc_query)
{
	return FPle(fc_range_box->left.low, fc_query->high) &&
		FPle(fc_range_box->right.low, fc_query->high);
}

/* range_box 中的任何范围是否可以高于此参数？ */
static bool fc_higher2D(RangeBox *fc_range_box, Range *fc_query)
{
	return FPgt(fc_range_box->left.high, fc_query->high) &&
		FPgt(fc_range_box->right.high, fc_query->high);
}

/* range_box 中的任何范围是否不能扩展到查询的左侧？ */
static bool fc_overHigher2D(RangeBox *fc_range_box, Range *fc_query)
{
	return FPge(fc_range_box->left.high, fc_query->low) &&
		FPge(fc_range_box->right.high, fc_query->low);
}

/* rect_box 中的任何矩形是否可以位于此参数的左侧？ */
static bool fc_left4D(RectBox *fc_rect_box, RangeBox *fc_query)
{
	return fc_lower2D(&fc_rect_box->range_box_x, &fc_query->left);
}

/* rect_box 中的任何矩形是否不延伸到此参数的右侧？ */
static bool fc_overLeft4D(RectBox *fc_rect_box, RangeBox *fc_query)
{
	return fc_overLower2D(&fc_rect_box->range_box_x, &fc_query->left);
}

/* rect_box 中的任何矩形是否可以位于此参数的右侧？ */
static bool fc_right4D(RectBox *fc_rect_box, RangeBox *fc_query)
{
	return fc_higher2D(&fc_rect_box->range_box_x, &fc_query->left);
}

/* rect_box 中的任何矩形是否不延伸到此参数的左侧？ */
static bool fc_overRight4D(RectBox *fc_rect_box, RangeBox *fc_query)
{
	return fc_overHigher2D(&fc_rect_box->range_box_x, &fc_query->left);
}

/* rect_box 中的任何矩形是否可以位于此参数的下方？ */
static bool fc_below4D(RectBox *fc_rect_box, RangeBox *fc_query)
{
	return fc_lower2D(&fc_rect_box->range_box_y, &fc_query->right);
}

/* rect_box 中的任何矩形是否不延伸到此参数的上方？ */
static bool fc_overBelow4D(RectBox *fc_rect_box, RangeBox *fc_query)
{
	return fc_overLower2D(&fc_rect_box->range_box_y, &fc_query->right);
}

/* rect_box 中的任何矩形是否可以位于此参数的上方？ */
static bool fc_above4D(RectBox *fc_rect_box, RangeBox *fc_query)
{
	return fc_higher2D(&fc_rect_box->range_box_y, &fc_query->right);
}

/* rect_box 中的任何矩形是否不延伸到此参数的下方？ */
static bool fc_overAbove4D(RectBox *fc_rect_box, RangeBox *fc_query)
{
	return fc_overHigher2D(&fc_rect_box->range_box_y, &fc_query->right);
}

/* 点与 rect_box 之间距离的下界 */
static double fc_pointToRectBoxDistance(Point *fc_point, RectBox *fc_rect_box)
{
	double		fc_dx;
	double		fc_dy;

	if (fc_point->x < fc_rect_box->range_box_x.left.low)
		fc_dx = fc_rect_box->range_box_x.left.low - fc_point->x;
	else if (fc_point->x > fc_rect_box->range_box_x.right.high)
		fc_dx = fc_point->x - fc_rect_box->range_box_x.right.high;
	else
		fc_dx = 0;

	if (fc_point->y < fc_rect_box->range_box_y.left.low)
		fc_dy = fc_rect_box->range_box_y.left.low - fc_point->y;
	else if (fc_point->y > fc_rect_box->range_box_y.right.high)
		fc_dy = fc_point->y - fc_rect_box->range_box_y.right.high;
	else
		fc_dy = 0;

	return HYPOT(fc_dx, fc_dy);
}


/*
 * SP-GiST 配置函数
 */
Datum spg_box_quad_config(PG_FUNCTION_ARGS)
{
	spgConfigOut *fc_cfg = (spgConfigOut *) PG_GETARG_POINTER(1);

	fc_cfg->prefixType = BOXOID;
	fc_cfg->labelType = VOIDOID;	/* 我们不需要节点标签。 */
	fc_cfg->canReturnData = true;
	fc_cfg->longValuesOK = false;

	PG_RETURN_VOID();
}

/*
 * SP-GiST 选择函数
 */
Datum spg_box_quad_choose(PG_FUNCTION_ARGS)
{
	spgChooseIn *fc_in = (spgChooseIn *) PG_GETARG_POINTER(0);
	spgChooseOut *fc_out = (spgChooseOut *) PG_GETARG_POINTER(1);
	BOX		   *fc_centroid = DatumGetBoxP(fc_in->prefixDatum),
			   *fc_box = DatumGetBoxP(fc_in->leafDatum);

	fc_out->resultType = spgMatchNode;
	fc_out->result.matchNode.restDatum = BoxPGetDatum(fc_box);

	/* nodeN 将由核心设置，当 allTheSame 时。 */
	if (!fc_in->allTheSame)
		fc_out->result.matchNode.nodeN = fc_getQuadrant(fc_centroid, fc_box);

	PG_RETURN_VOID();
}

/*
 * SP-GiST 拆分选择函数
 *
 * 它通过选择 4D 中心点作为盒子坐标的中位数来将一组盒子分成象限。
 */
Datum spg_box_quad_picksplit(PG_FUNCTION_ARGS)
{
	spgPickSplitIn *fc_in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
	spgPickSplitOut *fc_out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
	BOX		   *fc_centroid;
	int			fc_median,
				fc_i;
	float8	   *fc_lowXs = palloc(sizeof(float8) * fc_in->nTuples);
	float8	   *fc_highXs = palloc(sizeof(float8) * fc_in->nTuples);
	float8	   *fc_lowYs = palloc(sizeof(float8) * fc_in->nTuples);
	float8	   *fc_highYs = palloc(sizeof(float8) * fc_in->nTuples);

	/* 计算所有 4D 坐标的中位数 */
	for (fc_i = 0; fc_i < fc_in->nTuples; fc_i++)
	{
		BOX		   *fc_box = DatumGetBoxP(fc_in->datums[fc_i]);

		fc_lowXs[fc_i] = fc_box->low.x;
		fc_highXs[fc_i] = fc_box->high.x;
		fc_lowYs[fc_i] = fc_box->low.y;
		fc_highYs[fc_i] = fc_box->high.y;
	}

	qsort(fc_lowXs, fc_in->nTuples, sizeof(float8), fc_compareDoubles);
	qsort(fc_highXs, fc_in->nTuples, sizeof(float8), fc_compareDoubles);
	qsort(fc_lowYs, fc_in->nTuples, sizeof(float8), fc_compareDoubles);
	qsort(fc_highYs, fc_in->nTuples, sizeof(float8), fc_compareDoubles);

	fc_median = fc_in->nTuples / 2;

	fc_centroid = palloc(sizeof(BOX));

	fc_centroid->low.x = fc_lowXs[fc_median];
	fc_centroid->high.x = fc_highXs[fc_median];
	fc_centroid->low.y = fc_lowYs[fc_median];
	fc_centroid->high.y = fc_highYs[fc_median];

	/* 填充输出 */
	fc_out->hasPrefix = true;
	fc_out->prefixDatum = BoxPGetDatum(fc_centroid);

	fc_out->nNodes = 16;
	fc_out->nodeLabels = NULL;		/* 我们不需要节点标签。 */

	fc_out->mapTuplesToNodes = palloc(sizeof(int) * fc_in->nTuples);
	fc_out->leafTupleDatums = palloc(sizeof(Datum) * fc_in->nTuples);

	/*
	 * 根据与“质心”范围相对的象限，将范围分配给相应的节点
	 */
	for (fc_i = 0; fc_i < fc_in->nTuples; fc_i++)
	{
		BOX		   *fc_box = DatumGetBoxP(fc_in->datums[fc_i]);
		uint8		fc_quadrant = fc_getQuadrant(fc_centroid, fc_box);

		fc_out->leafTupleDatums[fc_i] = BoxPGetDatum(fc_box);
		fc_out->mapTuplesToNodes[fc_i] = fc_quadrant;
	}

	PG_RETURN_VOID();
}

/*
 * 检查基于边界框的一致性方法的结果是否准确。
 */
static bool fc_is_bounding_box_test_exact(StrategyNumber fc_strategy)
{
	switch (fc_strategy)
	{
		case RTLeftStrategyNumber:
		case RTOverLeftStrategyNumber:
		case RTOverRightStrategyNumber:
		case RTRightStrategyNumber:
		case RTOverBelowStrategyNumber:
		case RTBelowStrategyNumber:
		case RTAboveStrategyNumber:
		case RTOverAboveStrategyNumber:
			return true;

		default:
			return false;
	}
}

/*
 * 获取ScanKey的边界框。
 */
static BOX *
fc_spg_box_quad_get_scankey_bbox(ScanKey fc_sk, bool *fc_recheck)
{
	switch (fc_sk->sk_subtype)
	{
		case BOXOID:
			return DatumGetBoxP(fc_sk->sk_argument);

		case POLYGONOID:
			if (fc_recheck && !fc_is_bounding_box_test_exact(fc_sk->sk_strategy))
				*fc_recheck = true;
			return &DatumGetPolygonP(fc_sk->sk_argument)->boundbox;

		default:
			elog(ERROR, "unrecognized scankey subtype: %d", fc_sk->sk_subtype);
			return NULL;
	}
}

/*
 * SP-GiST内部一致性函数
 */
Datum spg_box_quad_inner_consistent(PG_FUNCTION_ARGS)
{
	spgInnerConsistentIn *fc_in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
	spgInnerConsistentOut *fc_out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
	int			fc_i;
	MemoryContext fc_old_ctx;
	RectBox    *fc_rect_box;
	uint8		fc_quadrant;
	RangeBox   *fc_centroid,
			  **fc_queries;

	/*
	 * 我们正在保存遍历值或将其初始化为一个无界的值，如果
	 * 我们刚刚开始遍历树。
	 */
	if (fc_in->traversalValue)
		fc_rect_box = fc_in->traversalValue;
	else
		fc_rect_box = fc_initRectBox();

	if (fc_in->allTheSame)
	{
		/* 报告所有节点都应该被访问 */
		fc_out->nNodes = fc_in->nNodes;
		fc_out->nodeNumbers = (int *) palloc(sizeof(int) * fc_in->nNodes);
		for (fc_i = 0; fc_i < fc_in->nNodes; fc_i++)
			fc_out->nodeNumbers[fc_i] = fc_i;

		if (fc_in->norderbys > 0 && fc_in->nNodes > 0)
		{
			double	   *fc_distances = palloc(sizeof(double) * fc_in->norderbys);
			int			fc_j;

			for (fc_j = 0; fc_j < fc_in->norderbys; fc_j++)
			{
				Point	   *fc_pt = DatumGetPointP(fc_in->orderbys[fc_j].sk_argument);

				fc_distances[fc_j] = fc_pointToRectBoxDistance(fc_pt, fc_rect_box);
			}

			fc_out->distances = (double **) palloc(sizeof(double *) * fc_in->nNodes);
			fc_out->distances[0] = fc_distances;

			for (fc_i = 1; fc_i < fc_in->nNodes; fc_i++)
			{
				fc_out->distances[fc_i] = palloc(sizeof(double) * fc_in->norderbys);
				memcpy(fc_out->distances[fc_i], fc_distances,
					   sizeof(double) * fc_in->norderbys);
			}
		}

		PG_RETURN_VOID();
	}

	/*
	 * 我们将前缀和查询转换为RangeBoxes，以便于进行后续操作。
	 */
	fc_centroid = fc_getRangeBox(DatumGetBoxP(fc_in->prefixDatum));
	fc_queries = (RangeBox **) palloc(fc_in->nkeys * sizeof(RangeBox *));
	for (fc_i = 0; fc_i < fc_in->nkeys; fc_i++)
	{
		BOX		   *fc_box = fc_spg_box_quad_get_scankey_bbox(&fc_in->scankeys[fc_i], NULL);

		fc_queries[fc_i] = fc_getRangeBox(fc_box);
	}

	/* 为节点分配足够的内存 */
	fc_out->nNodes = 0;
	fc_out->nodeNumbers = (int *) palloc(sizeof(int) * fc_in->nNodes);
	fc_out->traversalValues = (void **) palloc(sizeof(void *) * fc_in->nNodes);
	if (fc_in->norderbys > 0)
		fc_out->distances = (double **) palloc(sizeof(double *) * fc_in->nNodes);

	/*
	 * 我们切换内存上下文，因为我们想为新的遍历值（next_rect_box）分配内存，并将这些内存块传递给
	 * 此函数的进一步调用。
	 */
	fc_old_ctx = MemoryContextSwitchTo(fc_in->traversalMemoryContext);

	for (fc_quadrant = 0; fc_quadrant < fc_in->nNodes; fc_quadrant++)
	{
		RectBox    *fc_next_rect_box = fc_nextRectBox(fc_rect_box, fc_centroid, fc_quadrant);
		bool		fc_flag = true;

		for (fc_i = 0; fc_i < fc_in->nkeys; fc_i++)
		{
			StrategyNumber fc_strategy = fc_in->scankeys[fc_i].sk_strategy;

			switch (fc_strategy)
			{
				case RTOverlapStrategyNumber:
					fc_flag = fc_overlap4D(fc_next_rect_box, fc_queries[fc_i]);
					break;

				case RTContainsStrategyNumber:
					fc_flag = fc_contain4D(fc_next_rect_box, fc_queries[fc_i]);
					break;

				case RTSameStrategyNumber:
				case RTContainedByStrategyNumber:
					fc_flag = fc_contained4D(fc_next_rect_box, fc_queries[fc_i]);
					break;

				case RTLeftStrategyNumber:
					fc_flag = fc_left4D(fc_next_rect_box, fc_queries[fc_i]);
					break;

				case RTOverLeftStrategyNumber:
					fc_flag = fc_overLeft4D(fc_next_rect_box, fc_queries[fc_i]);
					break;

				case RTRightStrategyNumber:
					fc_flag = fc_right4D(fc_next_rect_box, fc_queries[fc_i]);
					break;

				case RTOverRightStrategyNumber:
					fc_flag = fc_overRight4D(fc_next_rect_box, fc_queries[fc_i]);
					break;

				case RTAboveStrategyNumber:
					fc_flag = fc_above4D(fc_next_rect_box, fc_queries[fc_i]);
					break;

				case RTOverAboveStrategyNumber:
					fc_flag = fc_overAbove4D(fc_next_rect_box, fc_queries[fc_i]);
					break;

				case RTBelowStrategyNumber:
					fc_flag = fc_below4D(fc_next_rect_box, fc_queries[fc_i]);
					break;

				case RTOverBelowStrategyNumber:
					fc_flag = fc_overBelow4D(fc_next_rect_box, fc_queries[fc_i]);
					break;

				default:
					elog(ERROR, "unrecognized strategy: %d", fc_strategy);
			}

			/* 如果任何检查失败，我们就找到了答案。 */
			if (!fc_flag)
				break;
		}

		if (fc_flag)
		{
			fc_out->traversalValues[fc_out->nNodes] = fc_next_rect_box;
			fc_out->nodeNumbers[fc_out->nNodes] = fc_quadrant;

			if (fc_in->norderbys > 0)
			{
				double	   *fc_distances = palloc(sizeof(double) * fc_in->norderbys);
				int			fc_j;

				fc_out->distances[fc_out->nNodes] = fc_distances;

				for (fc_j = 0; fc_j < fc_in->norderbys; fc_j++)
				{
					Point	   *fc_pt = DatumGetPointP(fc_in->orderbys[fc_j].sk_argument);

					fc_distances[fc_j] = fc_pointToRectBoxDistance(fc_pt, fc_next_rect_box);
				}
			}

			fc_out->nNodes++;
		}
		else
		{
			/*
			 * 如果这个节点没有被选择，我们不需要在内存上下文中保持下一个遍历值。
			 */
			pfree(fc_next_rect_box);
		}
	}

	/* 切换回来 */
	MemoryContextSwitchTo(fc_old_ctx);

	PG_RETURN_VOID();
}

/*
 * SP-GiST内部一致性函数
 */
Datum spg_box_quad_leaf_consistent(PG_FUNCTION_ARGS)
{
	spgLeafConsistentIn *fc_in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
	spgLeafConsistentOut *fc_out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
	Datum		fc_leaf = fc_in->leafDatum;
	bool		fc_flag = true;
	int			fc_i;

	/* 所有测试都是准确的。 */
	fc_out->recheck = false;

	/*
	 * 除非被告知，否则不要返回leafValue；这适用于框和
	 * 多边形操作类，在后者情况下，leaf datum甚至不是
	 * 返回的正确类型。
	 */
	if (fc_in->returnData)
		fc_out->leafValue = fc_leaf;

	/* 执行所需的比较 */
	for (fc_i = 0; fc_i < fc_in->nkeys; fc_i++)
	{
		StrategyNumber fc_strategy = fc_in->scankeys[fc_i].sk_strategy;
		BOX		   *fc_box = fc_spg_box_quad_get_scankey_bbox(&fc_in->scankeys[fc_i],
														&fc_out->recheck);
		Datum		fc_query = BoxPGetDatum(fc_box);

		switch (fc_strategy)
		{
			case RTOverlapStrategyNumber:
				fc_flag = DatumGetBool(DirectFunctionCall2(box_overlap, fc_leaf,
														fc_query));
				break;

			case RTContainsStrategyNumber:
				fc_flag = DatumGetBool(DirectFunctionCall2(box_contain, fc_leaf,
														fc_query));
				break;

			case RTContainedByStrategyNumber:
				fc_flag = DatumGetBool(DirectFunctionCall2(box_contained, fc_leaf,
														fc_query));
				break;

			case RTSameStrategyNumber:
				fc_flag = DatumGetBool(DirectFunctionCall2(box_same, fc_leaf,
														fc_query));
				break;

			case RTLeftStrategyNumber:
				fc_flag = DatumGetBool(DirectFunctionCall2(box_left, fc_leaf,
														fc_query));
				break;

			case RTOverLeftStrategyNumber:
				fc_flag = DatumGetBool(DirectFunctionCall2(box_overleft, fc_leaf,
														fc_query));
				break;

			case RTRightStrategyNumber:
				fc_flag = DatumGetBool(DirectFunctionCall2(box_right, fc_leaf,
														fc_query));
				break;

			case RTOverRightStrategyNumber:
				fc_flag = DatumGetBool(DirectFunctionCall2(box_overright, fc_leaf,
														fc_query));
				break;

			case RTAboveStrategyNumber:
				fc_flag = DatumGetBool(DirectFunctionCall2(box_above, fc_leaf,
														fc_query));
				break;

			case RTOverAboveStrategyNumber:
				fc_flag = DatumGetBool(DirectFunctionCall2(box_overabove, fc_leaf,
														fc_query));
				break;

			case RTBelowStrategyNumber:
				fc_flag = DatumGetBool(DirectFunctionCall2(box_below, fc_leaf,
														fc_query));
				break;

			case RTOverBelowStrategyNumber:
				fc_flag = DatumGetBool(DirectFunctionCall2(box_overbelow, fc_leaf,
														fc_query));
				break;

			default:
				elog(ERROR, "unrecognized strategy: %d", fc_strategy);
		}

		/* 如果任何检查失败，我们就找到了答案。 */
		if (!fc_flag)
			break;
	}

	if (fc_flag && fc_in->norderbys > 0)
	{
		Oid			fc_distfnoid = fc_in->orderbys[0].sk_func.fn_oid;

		fc_out->distances = spg_key_orderbys_distances(fc_leaf, false,
													fc_in->orderbys, fc_in->norderbys);

		/* 计算到多边形的距离时需要重新检查 */
		fc_out->recheckDistances = fc_distfnoid == F_DIST_POLYP;
	}

	PG_RETURN_BOOL(fc_flag);
}


/*
 * SP-GiST配置函数，用于以边界框方式损失表示的2-D类型
 */
Datum spg_bbox_quad_config(PG_FUNCTION_ARGS)
{
	spgConfigOut *fc_cfg = (spgConfigOut *) PG_GETARG_POINTER(1);

	fc_cfg->prefixType = BOXOID;	/* 由其边界框表示的类型 */
	fc_cfg->labelType = VOIDOID;	/* 我们不需要节点标签。 */
	fc_cfg->leafType = BOXOID;
	fc_cfg->canReturnData = false;
	fc_cfg->longValuesOK = false;

	PG_RETURN_VOID();
}

/*
 * SP-GiST压缩函数，用于多边形
 */
Datum spg_poly_quad_compress(PG_FUNCTION_ARGS)
{
	POLYGON    *fc_polygon = PG_GETARG_POLYGON_P(0);
	BOX		   *fc_box;

	fc_box = (BOX *) palloc(sizeof(BOX));
	*fc_box = fc_polygon->boundbox;

	PG_RETURN_BOX_P(fc_box);
}
